`:top

Das `!lineare Komplementaritätsproblem`! (`*LKP`*, `F33f`_`[engl.`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Englische_Sprache]`_`f `*linear complementarity problem`*) ist ein mathematisches Problem aus der `F33f`_`[Linearen Algebra`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Lineare_Algebra]`_`f.

Gegeben sei eine reelle Matrix M ∈ ∈ R n × × n {\\displaystyle M\\in \\mathbb {R} ^{n\\times n}} und ein reeller Vektor q ∈ ∈ R n {\\displaystyle q\\in \\mathbb {R} ^{n}} , dann finde Vektoren x , y ∈ ∈ R n {\\displaystyle x,y\\in \\mathbb {R} ^{n}} so, dass die drei Bedingungen gelten:

y = M x + q , x , y ≥ ≥ 0 , x i y i = 0 {\\displaystyle y=Mx+q~,~~x,y\\geq 0~,~~x_{i}y_{i}=0} für alle i {\\displaystyle i}

Eine eindeutige Lösung für dieses Problem existiert genau dann, wenn M eine P-Matrix ist, das heißt, dass alle prinzipalen `F33f`_`[Minoren`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Minor_(Mathematik)]`_`f der Matrix M strikt positiv sind. Verschiedene `F33f`_`[Algorithmen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Algorithmus]`_`f (u. a. Lemkes Algorithmus, oder mittels Unique Sink Orientations) zur Lösung von linearen Komplementaritätsproblemen sind bekannt.

Lineare Komplementaritätsprobleme tauchen in der Praxis z. B. in der `F33f`_`[Spieltheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Spieltheorie]`_`f oder als `F33f`_`[Optimalitätsbedingungen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Optimierung_(Mathematik)]`_`f (KKT) eines `F33f`_`[quadratischen Programms`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Quadratisches_Programm]`_`f auf.

Das Problem wurde 1968 von Richard Warren Cottle und `F33f`_`[George Dantzig`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=George_Dantzig]`_`f eingeführt.

>>Literatur

• Richard W. Cottle, `F33f`_`[Jong-Shi Pang`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Jong-Shi_Pang]`_`f, Richard E. Stone: The linear complementarity problem, Academic Press 1992, SIAM 2009

`c`F0af`_`[↑ Back to top`#top]`_`f`a